package _二分系列;

import java.util.Arrays;

/**
 * @Author: 吕庆龙
 * @Date: 2020/8/16 21:57
 * <p>
 * 题目描述: 小球间磁力最大化的最小值
 */
public class _5489 {

    public static void main(String[] args) {
        int[] p = new int[]{1,2,3,4,7};
        int m = 3;
        maxDistance(p,m );
    }

    /**
     * https://leetcode-cn.com/problems/magnetic-force-between-two-balls/solution/suo-yi-wei-shi-yao-yong-er-fen-ni-by-peng-peng-22/
     * https://leetcode-cn.com/problems/magnetic-force-between-two-balls/solution/c-er-fen-sou-suo-ying-gai-neng-gei-ni-jiang-ming-b/
     * 输入：position = [1,2,3,4,7], m = 3
     * 输出：3
     * 解释：将 3 个球分别放入位于 1，4 和 7 的三个篮子，两球间的磁力分别为 [3, 3, 6]。最小磁力为 3 。我们没办法让最小磁力大于 3 。
     */
    public static int maxDistance(int[] position, int m) {
        Arrays.sort(position);
        int min = 1;   //最小磁力的最小可能取值
        ////最小磁力的最大可能取值
        int max = (position[position.length - 1] - position[0]) / (m - 1);
        int res = 0;

        while (min <= max) { //有人这里写min < max 我觉得不太好理解，
            int mid = min + ((max - min) >> 1);
            if (check(position, mid, m)) {
                res = mid;
                min = mid + 1;
            } else {
                max = mid - 1;
            }
        }


        return res;
    }

    //这里其实是个贪心
    public static boolean check(int[] position, int curDistance, int m) {
        int pre = position[0];
        int count = 0;
        for (int i = 1; i < position.length; i++) {
            if (position[i] - pre >= curDistance) {
                count++;
                if (count >= m - 1) { //说明这个curDistance是可行的
                    return true;
                }
                pre = position[i];
            }

        }

        return false;
    }


}

